package tree.leetcode_113_medium_backtrace;

import java.util.ArrayList;
import java.util.List;

public class BackTraceDebug {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(13);
        pathSum(root,13);
    }
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        dfs(root, sum, path, res);
        return res;
    }

    public static void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }

        path.add(root.val);
        if (root.left == null && root.right == null && sum == root.val) {
            //引用类型，path集合会在递归过程中被不断改变，所以此时需要new一个来保存此时path的结果。
            res.add(new ArrayList<>(path));
            //此时这条路径和 等于 目标和， 把最后一个节点remove掉，因为以后都用不到了。
            path.remove(path.size() - 1);
            return;
        }
        dfs(root.left, sum - root.val, path, res);
        dfs(root.right, sum - root.val, path, res);
        //递归在向下的过程，最终是要返回给上级的，当前值使用完之后，把它删除，也就是"剪枝"
        path.remove(path.size() - 1);
    }
}
